package leet20validparentheses

// 思路：
// 括号匹配的经典解决思路就是栈
// 我们将字符逐个遍历并入栈左括号，右括号是不需要入栈的，我们需要判断右括号与栈顶字符是否匹配(匹配的意思是当前字符是右括号，栈顶字符是左括号)
// 如果匹配则出栈，说明无论是类型还是位置都匹配成功了；如果不匹配则说明最近一个右括号与栈顶左括号不匹配，说明括号不匹配了，那么之后也不肯匹配了，直接返回 false

// 复杂度分析：
// 时间复杂度：O(n)，其中 n 为字符串长度
// 空间复杂度：O(n)，栈的大小为 n

func IsValid(s string) bool {
	// 定义一个栈
	stack := make([]rune, 0)
	// 定义一个映射表，存储括号的对应关系
	mapping := map[rune]rune{
		')': '(',
		']': '[',
		'}': '{',
	}
	for _, char := range s {
		if char == '(' || char == '[' || char == '{' {
			stack = append(stack, char)
		} else { // 当前分支表示符号都是右括号
			// 如果栈为空，肯定就无法匹配了，说明已经被别人匹配走了
			// 如果栈顶元素不是当前字符的左括号，则说明括号不匹配，栈内元素就永远无法匹配了，所以只能返回 false
			if len(stack) == 0 || stack[len(stack)-1] != mapping[char] {
				return false
			}
			// 执行到这里说明栈顶元素是当前字符的左括号，说明匹配成功，那么就出栈。
			stack = stack[:len(stack)-1]
		}
	}
	return len(stack) == 0
}
